/**
 * 给定若干个正方形，求一条水平线恰好平分上下面积，重叠区域要重复计算
 * 显然是二分。
 * 但是实数域二分，所以不写dowhile循环，直接循环100次一般肯定够用。
 * 其实只需要循环接近50次即可
 */

double const EPS = 1E-7;
int sgn(double x){return (x > EPS ? 1 : (x < -EPS? -1 : 0));}

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        double left = 1E100;
        double right = -1;
        double total = 0;
        for(const auto & v : squares){
            left = min(left, (double)v[0]);
            right = max(right, (double)(v[1] + v[2]));
            total += (double)v[2] * v[2];
        }   
        auto fAbove = [&squares](double mid)->double{
            double ans = 0;
            for(const auto & v : squares){
                if(mid < v[1]) ans += (double)v[2] * v[2];
                else if(mid < v[1] + v[2]){
                    double cha = v[1] + v[2] - mid;
                    ans += cha * v[2];
                } 
            }
            return ans;
        };
        double mid;         
        for(int i=0;i<100;++i){
            mid = (left + right) * 0.5;    
            auto shang = fAbove(mid);
            auto xia = total - shang;
            int t = sgn(shang - xia);
            if(t > 0) left = mid;
            else right = mid;
        }
        return right;
    }
};